﻿#ifndef XQUICKSORT_H
#define XQUICKSORT_H
#include<iostream>
#include<stack>
//快速排序
template<typename _RanIt, typename _Pr>
void XQuickSort(const _RanIt _First, const _RanIt _Last, _Pr _Pred);
//三数取中
template<typename _RanIt, typename _Pr>
static _RanIt GetMidIndex(const _RanIt _First, const _RanIt _Last, _Pr _Pred);
//快排挖坑排序单次
template<typename _RanIt, typename _Pr>
static _RanIt QuicPitSort_One(const _RanIt _First, const _RanIt _Last, _Pr _Pred);

template<typename _RanIt, typename _Pr>
inline void XQuickSort(const _RanIt _First, const _RanIt _Last, _Pr _Pred)
{
	if (_First == nullptr || _Last == nullptr)
		return;
	std::stack<_RanIt> stack;
	_RanIt begin = _First;//头
	_RanIt end = _Last;//尾元素
	_RanIt temp = nullptr;//入栈边界临时迭代器
	stack.push(end);//入右边界
	stack.push(begin);//入左边界
	_RanIt left = nullptr;//区间头迭代器
	_RanIt right = nullptr;//区间尾迭代器
	_RanIt pivit = nullptr;//单次排序返回的排好元素迭代器
	while (!stack.empty())
	{
		left = stack.top();stack.pop();
		right = stack.top();stack.pop();
		pivit= QuicPitSort_One(left, right, _Pred);
		temp = pivit + 1;
		if (temp < right)//右区间存在
		{
			stack.push(right);//入右边界
			stack.push(temp);//入左边界
		}
		temp = pivit - 1;
		if (left < temp)//左区间存在
		{
			stack.push(pivit);//入右边界
			stack.push(left);//入左边界
		}
	}
}

template<typename _RanIt, typename _Pr>
inline _RanIt GetMidIndex(const _RanIt _First, const _RanIt _Last, _Pr _Pred)
{
	size_t count = _Last - _First;//数据总量
	auto _mid = _First + (count/2);//取中间值
	auto  _end = _Last - 1;//最后一个
	//假设<
	if (_Pred(*_First, *_mid))
	{//_First<_mid 
		if (_Pred(*_mid,*_end))
			return _mid;//_First<_mid< _end
		else if (_Pred(*_First, *_end))//_First<_mid &&_mid>_end  
			return _end;//_First<_mid &&_mid>_end &&_First< _end  _First最小的 _mid最大的 _First<_end<_mid
		else
			return _First;//_First<_mid &&_mid>_end &&_First> _end  _mid最大的 _end<_First<_mid
	}
	else
	{//_mid<_First 
		if (_Pred(*_First, *_end))
			return _First;//_mid<_First <_end
		else if (_Pred(*_mid, *_end))//_mid<_First&&_First>_end  _First是最大的
			return _end;//_mid<_end<_First
		else
			return _mid;//_end<<_mid<_First
	}
}
template<typename _RanIt, typename _Pr>
inline _RanIt QuicPitSort_One(const _RanIt _First, const _RanIt _Last, _Pr _Pred)
{
	_RanIt _mid = GetMidIndex(_First, _Last, _Pred);
	std::swap(*_First, *_mid);
	_RanIt begin = _First;//头迭代器
	_RanIt end = _Last-1;//尾迭代器
	_RanIt pivit = begin;//坑位置
	while (begin < end)
	{
		//flag = true;
		//右边找放左边
		while (begin < end && !_Pred(*end, *pivit))
		{
			end--;
		}
		if (begin < end)
		{
			std::swap(*pivit, *end);//交换函数,入坑
			pivit = end;//新的坑位
		}
		//左边找放右边
		while (begin < end && _Pred(*begin, *pivit) )
		{
			begin++;
		}
		if (begin < end)
		{
			std::swap(*pivit, *begin);//交换函数,入坑
			pivit = begin;//新的坑位
		}
	}
	return pivit;
}
#endif // !XSORT_H